package com.cdy.demo.algorithm;

public class Leetcode5 {

	public static void main(String[] args) {
		Leetcode5 Leetcode5 = new Leetcode5();
	}

	/**
	 * 5 回文字符
	 *
	 * @param s
	 * @return
	 */
	public String longestPalindrome(String s) {
		int len = s.length();
		if (len == 0) {
			return "";
		}
		//  i-》j 之前的字符串是不是回文字符串
		boolean[][] dp = new boolean[len][len];
		for (int i = 0; i < len; i++) {
			dp[i][i] = true;// 自己肯定时回文的
		}

		String res = s.substring(0, 1);
		int max = 0;
		//从含义上来讲 ，  终点先不变， 起点一次靠近重点
		//从矩阵来说， 先填充横向的， 状态转移是去上一行的数据
		for (int j = 1; j < len; j++) {
			for (int i = 0; i < j; i++) {

				boolean b = s.charAt(i) == s.charAt(j);
				if (j - i >= 3) {
					//
					dp[i][j] = b && dp[i + 1][j - 1];
				} else {
					dp[i][j] = b;
				}
				if (dp[i][j]) {
					if (j - i + 1 > max) {
						max = j - i + 1;
						res = s.substring(i, j + 1);
					}
				}
			}
		}
		return res;

	}


	/**
	 * 10  正则匹配
	 *
	 * @param s
	 * @param p
	 * @return
	 */
	public boolean isMatch(String s, String p) {

		int slen = s.length();
		int plen = p.length();
		// dp[i][j] 为 s从i到最后，p从j到最后 是否两者匹配
		boolean[][] dp = new boolean[slen + 1][plen + 1];


		for (int i = slen; i >= 0; i--) {
			for (int j = plen; j >= 0; j--) {
				if (i == slen && j == plen) {
					continue;
				}

				boolean match = (i < slen && j < plen) && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');

				if (j + 1 < plen && p.charAt(j + 1) == '*') {
					dp[i][j] = dp[i][j + 2] || (match && dp[i + 1][j]);
				} else {
					dp[i][j] = match && dp[i + 1][j + 1];
				}


			}

		}


		return dp[0][0];


	}


	/**
	 * 72  单词转换
	 *
	 * @param word1
	 * @param word2
	 * @return
	 */
	public int minDistance(String word1, String word2) {

		int len = word1.length();
		int len2 = word2.length();

		// dp[i][j] 表示 word1从0-i和word2 从0-j 转换的次数
		int[][] dp = new int[len + 1][len2 + 1];
		dp[0][0] = 1;
		for (int i = 0; i < len + 1; i++) {
			dp[i][0] = i;
		}
		for (int i = 0; i < len2 + 1; i++) {
			dp[0][i] = i;
		}

		for (int i = 1; i < len + 1; i++) {
			for (int j = 1; j < len2 + 1; j++) {
				if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
					dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1]));
				} else {
					// 增加一个， 删除一个，替换一个中最少的
					dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
				}
			}

		}

		return dp[len][len2];
	}

}
